#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int N = 2005,mod = 998244353,INF = 0x3f3f3f3f;
int n,m;
vector<int>e[N];
ll f[N],g[N];
int cnt,ans;
int dfn[N],low[N],dfcnt;
bool ins[N];
int stk[N],tp;
void Tarjan(int u)
{
    //cout<<"Tarjan"<<u<<"\n";
    stk[++tp] = u;
    ins[u] = 1;
    dfn[u] = low[u] = ++dfcnt;
    for(auto v:e[u])
    {
        if(!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u],low[v]);
            if(low[v] >= dfn[u])
            {
                int tmp = 0;
                while(stk[tp] != v)
                {
                    ins[stk[tp]] = 0;
                    tp--;
                    tmp++;
                }
                ins[v] = 0;
                tp--;
                tmp += 2;
                //cout<<u<<" "<<v<<" "<<tmp<<"\n";
                if(tmp == 2) continue;
                //cout<<u<<" "<<v<<" "<<tmp<<"\n";
                if(tmp < ans) ans = tmp,cnt = 1;
                else if(tmp == ans) cnt++;
            }
        }
        else if(ins[v]) low[u] = min(low[u],dfn[v]);
    }
}
int c[N][N],d[N][N];
void check()
{
    for(int i = 1;i <= n;i++)
    {
        for(int j = i+1;j <= n;j++)
        {
            if(i == j) c[i][j] = 0;
            else if(d[i][j]) c[i][j] = c[j][i] = 1;
            else c[i][j] = c[j][i] = INF;
        }
    }
    for(int i = 1;i <= n;i++) for(int x = 1;x <= n;x++) for(int y = 1;y <= n;y++) c[x][y] = min(c[x][y],c[x][i] + c[i][y]);
    int tmp = 0;
    for(int i = 1;i <= n;i++) for(auto j:e[i]) if(j > i)
    {
        if(c[i][j] == INF) return;
        tmp += c[i][j];
    }
    if(tmp < ans) ans = tmp,cnt = 1;
    else if(tmp == ans) cnt++;
}
void work(int x,int y,int k)
{
    if(k >= m) return ;
    if(x == n && k == m-1) return check(),void();
    else if(x == n) return ;
    if(y == n)
    {
        d[x][y] = 1;
        work(x+1,x+2,k+1);
        d[x][y] = 0;
        work(x+1,x+2,k);
    }
    else
    {
        d[x][y] = 1;
        work(x,y+1,k+1);
        d[x][y] = 0;
        work(x,y+1,k);
    }
}
int main()
{
    freopen("oi.in","r",stdin);
    freopen("oi.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(0);
    int C,T;cin>>C>>T;
    while(T--)
    {
        cin>>n>>m;
        tp = 0;
        for(int i = 1;i <= n;i++) e[i].clear(),ins[i] = dfn[i] = low[i] = 0;
        for(int i = 1;i <= m;i++)
        {
            int u,v;cin>>u>>v;
            e[u].pb(v),e[v].pb(u);
        }
        if(C <= 2)
        {
            ans = INF,cnt = 0;
            work(1,2,0);
            cout<<-ans<<" "<<cnt<<"\n";
            continue;
        }
        g[1] = f[1] = 1;
        for(int i = 2;i <= n;i++)
        {
            f[i] = g[i] = 0;
            for(int j = 1;j < i;j++)
            {
                g[i] = (g[i] + f[j]*g[i-j])%mod;
            }
            for(int j = 0;j < i;j++)
            {
                f[i] = (f[i] + g[j+1]*g[i-j])%mod;
            }
            //cout<<j<<" "
        }
        //cout<<-2*n+2<<" "<<g[n]<<"\n";
        if(C == 3 || C == 4) cout<<-2*n+2<<" "<<g[n]<<"\n";
        if(C == 5 || C == 6)
        {
            ans = n+1,cnt = 0;
            for(int i = 1;i <= n;i++) if(!dfn[i]) Tarjan(i);
            cout<<-m-ans+2<<" "<<cnt*g[ans]%mod<<"\n";
        }
    }
    return 0;
}
/*
5 1
6 6
1 5
1 3
3 4
1 6
3 2
2 5
*/